﻿#include <iostream>
#include <assert.h>

#define INVALID_VALUE 0x1fffffff
#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)

static int recurUseMinBags(int remain)
{
	switch (remain)
	{
	case 0:
		return 0;

	case -1:
	case -2:
	case 1:
	case 2:
	case 3:
	case 4:
	case 5:
	case 7:
	case 9:
	case 10:
	case 11:
	case 13:
		return INVALID_VALUE;
	}

	int use6 = 1 + recurUseMinBags(remain - 6);
	int use8 = 1 + recurUseMinBags(remain - 8);
	return MIN(use6, use8);
}

static int useMinBags(int total)
{
	int res = recurUseMinBags(total);
	if (res >= INVALID_VALUE) return -1;
	return res;
}

static int byStrictTable(int total)
{
	int* dp = (int*)malloc((total + 1) * sizeof(int));
	memset(dp, 0, (total + 1) * sizeof(int));

	for (int remain = 1; remain <= total; remain++)
	{
		switch (remain)
		{
		case 1:
		case 2:
		case 3:
		case 4:
		case 5:
		case 7:
		case 9:
		case 10:
		case 11:
		case 13:
			dp[remain] = INVALID_VALUE;
			break;

		default:
		{
			int use6 = 1 + ((remain - 6 >= 0) ? dp[remain - 6] : INVALID_VALUE);
			int use8 = 1 + ((remain - 8 >= 0) ? dp[remain - 8] : INVALID_VALUE);
			dp[remain] = MIN(use6, use8);
		}
			break;
		}
	}

	int res = dp[total];
	free(dp);
	if (res >= INVALID_VALUE)
	{
		return -1;
	}

	return res;
}

// 求解最小公倍数
static int lowestCommonMultiple(int a, int b)
{
	int larger = MAX(a, b);
	int smaller = MIN(a, b);
	for (int i = 1; i < smaller; i++)
	{
		if ((larger * i) % smaller == 0)
			return larger * i;
	}

	return larger * smaller;
}

static int greedy(int total)
{
	if (total % 2 != 0) return -1;

	switch (total)
	{
	case 2:
	case 4:
	case 10:
		return -1;
	}

	int n8 = total / 8;
	int left = total - 8 * n8;
	while (n8 >= 0 && left % 6 != 0)
	{
		--n8;
		left = total - 8 * n8;
	}

	if (left % 6 == 0)
	{
		return n8 + (left / 6);
	}

	return -1;
}

//  小虎去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装，包装不可拆分。
//  但是小虎现在只想购买恰好n个苹果，小虎想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小虎将不会购买。
//  输入一个整数n，表示小虎想购买多少个苹果，返回最小使用多少袋子。如果无论如何都不能正好装下，返回 -1。
// 
// 思路：先尽可能更多的使用容量8的袋子，剩下的看能否使用容量6的袋子装完；
//  如果有剩余，则将上一步的容量8袋子减少一个，再看剩下的能否使用容量6的袋子装完...
int main_BuyApples()
{
	for (int wanted = 1; wanted <= 60; wanted++)
	{
		int a = useMinBags(wanted);
		int b = byStrictTable(wanted);
		int c = greedy(wanted);
		assert(a == b && a == c && "Error found!");
		printf("[%d] %d %d %d\n", wanted, a, b, c);
	}

	return 0;
}